package com.chj.jz.dp.class02;

// https://www.lintcode.com/problem/bomb-enemy/description
public class Code08_BombEnemy {
	/**
	 * @param grid
	 *            Given a 2D grid, each cell is either 'W', 'E' or '0'
	 * @return an integer, the maximum enemies you can kill using one bomb
	 */
	public static int maxKilledEnemies(char[][] A) {
		if (A == null || A.length == 0 || A[0].length == 0) {
			return 0;
		}

		int m = A.length;
		int n = A[0].length;
		int[][] up = new int[m][n];
		int[][] down = new int[m][n];
		int[][] left = new int[m][n];
		int[][] right = new int[m][n];
		int i, j, res = 0;

		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (A[i][j] == 'W') {
					up[i][j] = 0;
					continue;
				}

//				System.out.println("A = "+ A[i][j]);
				up[i][j] = A[i][j] == 'E' ? 1 : 0;

				if (i > 0) {
					up[i][j] += up[i - 1][j];
				}
			}
		}

		for (i = m - 1; i >= 0; --i) {
			for (j = 0; j < n; ++j) {
				if (A[i][j] == 'W') {
					down[i][j] = 0;
					continue;
				}

				down[i][j] = A[i][j] == 'E' ? 1 : 0;

				if (i < m - 1) {
					down[i][j] += down[i + 1][j];
				}
			}
		}

		for (i = 0; i < m; ++i) {
			for (j = 0; j < n; ++j) {
				if (A[i][j] == 'W') {
					left[i][j] = 0;
					continue;
				}

				left[i][j] = A[i][j] == 'E' ? 1 : 0;

				if (j > 0) {
					left[i][j] += left[i][j - 1];
				}
			}
		}

		for (i = 0; i < m; ++i) {
			for (j = n - 1; j >= 0; --j) {
				if (A[i][j] == 'W') {
					right[i][j] = 0;
					continue;
				}

				right[i][j] = A[i][j] == 'E' ? 1 : 0;

				if (j < n - 1) {
					right[i][j] += right[i][j + 1];
				}
			}
		}

		for (i = 0; i < m; i++) {
			for (j = 0; j < n; j++) {
				if (A[i][j] == '0') {
					int t = up[i][j] + down[i][j] + left[i][j] + right[i][j];
//					System.out.println("t = "+ t);
					res = Math.max(t, res);
				}
			}
		}

		return res;
	}

	public static void main(String[] args) {
		{
			char[][] arr = new char[][] { { '0', 'E', '0', '0' }, { 'E', '0', 'W', 'E' }, { '0', 'E', '0', '0' } };
			System.out.println(maxKilledEnemies(arr));
		}
		{
			char[][] arr = new char[][] { { '0', 'E', '0', '0' }, { 'E', 'E', 'W', 'E' }, { '0', 'E', '0', '0' } };
			System.out.println(maxKilledEnemies(arr));
		}
	}
}
